// Problem 034: Circular primes
// The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.
// There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.
// How many circular primes are there below one million?

package main

import (
	"fmt"
	"projecteuler/euler"
	"strconv"
)

var candidates map[int]int = make(map[int]int)

func p035() {
	ans := 13
	if len(candidates) != 0 {
		candidates = make(map[int]int)
	}
	for l := 100; l <= 100000; l *= 10 {
		getCandidate(l, 0)
	}
	for k := range candidates {
		check035(k)
	}
	fmt.Println("Problem 035:", len(candidates)+ans)
}

func getCandidate(gt, n int) {
	if n > gt {
		if euler.IsPrime(n) {
			candidates[n] = 0
		}
		return
	}
	P := [4]int{1, 3, 7, 9}
	for i := 0; i < 4; i++ {
		getCandidate(gt, n*10+P[i])
	}
}

func check035(n int) {
	flag := true
	temp := []int{n}
	nlen := len(strconv.Itoa(n))
	for times := 1; times < nlen; times++ {
		m := n%10*euler.TenPower[nlen-1] + n/10
		n = m
		if _, ok := candidates[m]; ok {
			temp = append(temp, m)
		} else {
			flag = false
		}
	}
	if !flag {
		for _, v := range temp {
			delete(candidates, v)
		}
	}
}
